#include <bits/stdc++.h>
using namespace std;


const int INF = 1e8; // !!! 可以再增加一个bool数组来标识有没有线
int n;

int main(int argc, char const *argv[])
{
    freopen("dijkstra.txt", "r", stdin);

    cin >> n;
    
    int arr[n + 1][n + 1];
    int t;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> t;
            arr[i][j] = t == 0 ? INF : t;
        }
    }

    // for(int i = 1; i <= n; ++i){
    //     for(int j = 1; j <= n; ++j){
    //         cout << arr[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    int sid = 1;
    int S[n + 1]; S[1] = 0;
    int U[n + 1] = {0};
    bool flag[n + 1] = {false}; flag[sid] = true;
    for(int i = 1; i <= n; ++i){
        if(!flag[i]) U[i] = arr[sid][i];
        cout << U[i] << " ";
    }
    cout << endl;
    
    
    for(int i = 2; i <= n; ++i){
        // update S
        int minid, mindis = INF;
        for(int j = 1; j <= n; ++j){
            if(!flag[j] && U[j] < mindis){
                minid = j;
                mindis = U[j];
            }
        }
        S[minid] = mindis;
        flag[minid] = true;
        cout << minid << " " << mindis << endl;

        // update U
        for(int j = 1; j <= n; ++j){
            // cout << j << " - " << mindis + arr[minid][j] << endl;
            if(!flag[j] && mindis + arr[minid][j] < U[j]){
                U[j] = mindis + arr[minid][j];
                // cout << j << " " << U[j] << endl;
            }
        }
        // exit(0);
    }

    return 0;
}
